package leetcode

// Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
// Output: [3,9,20,null,null,15,7]
// https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
func buildTree(inorder []int, postorder []int) *TreeNode {
	inmap := make(map[int]int)
	for i, v := range inorder {
		inmap[v] = i
	}
	var dfs func(inl, inr, postl, postr int) *TreeNode
	dfs = func(inl, inr, postl, postr int) *TreeNode {
		if inl > inr {
			return nil
		}
		interval := inmap[postorder[postr]]
		root := &TreeNode{Val: postorder[postr]}
		root.Left = dfs(inl, interval-1, postl, postl+interval-inl-1)
		root.Right = dfs(interval+1, inr, postl+interval-inl, postr-1)
		return root
	}
	return dfs(0, len(inorder)-1, 0, len(postorder)-1)
}
